1. Field of the Invention
The present invention relates generally to image compression, and more particularly to a motion vector searching method using plural search areas.
2. Background of the Related Art
Generally, the core technique of multimedia is to compress information such as an image, sound, voice, text, general data, etc., in accordance with characteristics of the respective information. If the information is not compressed, it is difficult to transmit or store the information due to its excessive amount of data.
In compressing the image, the compression ratio can be heightened by allowing errors to go uncorrected that a human eye or ear can hardly perceive. Information compressed in this manner may be somewhat different from the original values during its restoration, but it does not matter if the difference is not detected by the human eye or ear.
Image compression is performed through removal of duplication imminent in the image data. The duplication imminent in the image data is briefly classified into three kinds. First, pictures of two adjacent frames are very similar to each other in the event that several frames are produced per second, and backgrounds of the pictures are the same except for a portion where motion exists. This is a temporal duplication existing between the pictures. Also, values of adjacent pixels in the picture are very similar to each other, and this is a spatial duplication existing between the pixels. The remaining one is a statistical duplication.
Generally, a motion vector search is used as an element that influences the performance of a moving image compressor. In case of performing a full area search, an extremely large amount of computations is consumed. Thus, diverse methods for high-speed motion searching have been introduced, and a motion searching section has been implemented by hardware.
As shown in FIG. 1, the core element of any motion estimation section has typical inputs and outputs irrespective of the hardware implementation, software implementation, and high-speed searching method.
A motion estimator of FIG. 1 receives pixel values (i.e., original data) O(k,l) of the present frame, pixel values P(k,l) of the previous frame restored from the compression, ranges of search areas (M0,N0) and (M1,N1), and block size (BS) as its inputs, determines a motion vector between the present frame and the previous frame and sum of absolute difference (SAD) among the search areas according to the relationship among the inputs, and outputs determined values.
The core of the motion vector search is to search the most similar area to a search area of the present frame from the previous frame, and can be expressed by the following Equation 1.
                                          SAD            ⁡                          (                              i                ,                j                            )                                =                                    ∑                              k                =                0                                            BS                -                1                                      ⁢                                          ∑                                  l                  =                  0                                                  BS                  -                  1                                            ⁢                                                                                    O                    ⁡                                          (                                              k                        ,                        l                                            )                                                        -                                      P                    ⁡                                          (                                                                        k                          +                          i                                                ,                                                  l                          +                          j                                                                    )                                                                                                                          ⁢                                  ⁢                              MV            =                          arg              ⁢                                                min                                      (                                          i                      ,                      j                                        )                                                  ⁢                                  (                                      SAD                    ⁡                                          (                                              i                        ,                        j                                            )                                                        )                                                              ,                      M0            ≤            i            ≤            M1                    ,                      N0            ≤            j            ≤            N1                                              [Equation  1]            
In Equation 1, the sum of absolute difference—(SAD) denotes a degree of similarity that is an index for measuring the similarity among the areas, and BS denotes the size of the block. (M0,N0) and (M1,N1) denote a tetragonal search area in the restored previous frame. Specifically, (M0,N0) denotes a left upper coordinate in the tetragonal search area, and (M1,N1) denotes a right lower coordinate in the tetragonal search area. Also, O(k,l) denotes pixel values of the present frame to be searched, and P(k,l) denotes pixel values of the restored previous frame.
Equation 1 is used for searching a motion vector from the pixel values O(k,l) of the present frame, the pixel values P(k,l) of the restored previous frame, and in the tetragonal ranges of the search areas (M0,N0) and (M1,N1).
The sum of absolute difference (SAD) that is an index for measuring the similarity among the areas is obtained as follows.
First, the pixel value P(k,l) of the restored previous frame is subtracted from the pixel value O(k,l) of the present frame to be searched using the search area ranges (M0,N0) and (M1,N1). This subtraction is performed with respect to all the pixels. Then, absolute values of the subtracted values are obtained, respectively, and then added together. The added value is the sum of absolute difference (SAD).
Thereafter, (i,j) corresponding to a minimum SAD value among the SAD values obtained with respect to the respective (i,j) is determined as the motion vector (MV) of the present frame. For example, it is assumed that the block size (BS) is 16, the left upper coordinate of the search area is (M0,N0)=(−16,−16), and the right lower coordinate of the search area is (M1,N1)=(15,15).
If an image having a firstly given resolution is supplied to the motion vector estimator 10 on the basis of the original point (0,0), a full motion vector search with respect to a macro block of MPEG-4 or H.263 begins. The full search has a good performance, but has a too much amount of computation.